package shuzu

func detectCycle(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return nil
	}
	dummy := &ListNode{Next: head}
	list := dummy.Next
	// 使用双指针
	circle, ok := JudgeCircle(list)
	if ok {
		for circle != list {
			circle = circle.Next
			list = list.Next
		}
		return circle
	}
	return nil
}

func JudgeCircle(head *ListNode) (*ListNode, bool) {
	fast, slow := head, head
	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
		if fast == slow {
			break
		}
	}
	if fast == slow {
		return fast, true
	}
	return nil, false
}
